package digui

import (
	"container/list"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	stack := list.New()
	ret := make([]int, 0)
	type stackNode struct {
		parent   *TreeNode
		nextOpId int
		cur      *TreeNode
	}

	visited := func(ele *TreeNode) {
		ret = append(ret, ele.Val)
	}
	node := &stackNode{
		parent:   nil,
		nextOpId: 0,
		cur:      root,
	}

	stack.PushBack(node)

	for stack.Len() > 0 {
		back := stack.Back().Value.(*stackNode)
		if back.cur == nil {
			stack.Remove(stack.Back())
			back = stack.Back().Value.(*stackNode)
		}
		operId := back.nextOpId

		if operId == 0 {
			back.nextOpId++

			temp := &stackNode{
				parent:   back.cur,
				cur:      back.cur.Left,
				nextOpId: 0,
			}
			stack.PushBack(temp)
		} else if operId == 1 {
			back.nextOpId++

			temp := &stackNode{
				parent:   back.cur,
				cur:      back.cur.Right,
				nextOpId: 0,
			}

			stack.PushBack(temp)
		} else if operId == 2 {
			visited(back.cur)
			stack.Remove(stack.Back())
		}
	}

	return ret
}
